1. Field of the Invention
The present invention relates to a Viterbi decoding apparatus for use in satellite broadcasting, etc.
2. Description of the Prior Art
Conventionally, Viterbi decoding has been known as one of methods for decoding convolutional codes. Viterbi decoding is the maximum likelihood decoding for convolutional codes and selects a code string (called a maximum likelihood path) which most resembles the received code string among those generated by an encoder on the sending side, thereby enabling error correction.
The maximum likelihood path is basically established not by comparing all paths with each other but by obtaining a Hamming distance between all the code strings generated on the sending side and the received code strings to select the path having the smallest Hamming distance cumulative value (that is, the path having the highest degree of likelihood), thereafter checking only those paths which are necessary for decoding (they are called surviving paths). When the lengths of paths are made sufficiently long, the tips (reversely called the roots) of surviving paths will join to be the same value, indicating that each surviving path retrospectively decodes the same value.
Consequently, if a path length is provided such that it will not increase a decoding error ratio, the data at the point of time retrospectively reached by the path length becomes a decode word, thus providing correct decode word reproduction.
FIG. 5 is a block diagram showing an example of a Viterbi decoding apparatus using the Viterbi decoding described above.
The Viterbi decoding apparatus shown comprises a branch metric calculating circuit 101, an ACS (Adder, Comparator, Selector) circuit 102, a normalizing circuit 103, a state metric memory circuit 104, a path memory circuit 105, and a maximum likelihood decode decision circuit 106. When data sent from the sending side (that is, the received data) is supplied to this Viterbi decoding apparatus, the code string most resembles the received code string is selected from among those generated by the encoder on the sending side (the most resembling code is called the maximum likelihood path) to generate decoded data based on the selection.
When the received data is supplied, the branch metric calculating circuit 101 calculates the branch metric of the receive data to send the result (branch metric) to the ACS circuit 102.
The ACS circuit 102, based on a branch metric supplied from the branch metric calculating circuit 101 and a state metric supplied from the state metric memory circuit 104, adds the Hamming distance (branch metric) between received code and path to the cumulative sum (state metric) of the branch metric obtained so far to compare the result with each of two paths joining into a certain state to select the path having a higher degree of likelihood. The ACS circuit 102 then supplies the resulting selection to the path memory circuit 105 and the newly obtained cumulative sum (state metric) to the normalizing circuit 103.
In this case, if a constraint length of "3" is provided, the Hamming distance (branch metric) between received code and path and the cumulative sum (state metric) of the branch metric obtained so far are added to each of the two paths joining into a certain state as shown in the transition diagram in FIG. 6 and are compared with each path for each time slot. The code having highest degree of likelihood is selected based on the comparison.
The normalizing circuit 103 normalizes the state metric output from the ACS circuit 102 to a level within a preset range to send the result to the state metric memory circuit 104.
The state metric memory circuit 104 stores the normalized state metric sent from the normalizing circuit 103 to send the state metric back to the ACS circuit 102.
The path memory circuit 105 stores the selection result output from the ACS circuit 102 to supply it to the maximum likelihood decode decision circuit 106.
The maximum likelihood decode decision circuit 106 determines the maximum likelihood path based on the data stored in the path memory circuit 105 and generates the decoded data to be output.
It should be noted here that the prior art Viterbi decoding apparatus described above must select the path having the smallest state metric from among the path strings stored in the path memory circuit 105 in order to have the maximum likelihood decode decision circuit 106 select the decode word (decoded data) having the highest degree of likelihood.
With the prior art Viterbi decoding apparatus, however, each decoding operation must be performed at the speeds lower than an average information rate. Consequently, when decoding a code string having a very high transmission rate and a long constraint length, too many states resulted make it often difficult to select the maximum likelihood path in time.
For example, if a constraint length is seven bits, the path having the highest degree of likelihood must be selected from among 64 state metrics corresponding to these seven bits, thereby making the decision time long.
For this reason, the prior art apparatus cannot make maximum likelihood decision for decoding within an average information rate in processing information amounting to 30 Mbps or more when decoding convolutional codes used for high-definition TV, etc.
To overcome this problem, several methods have been proposed: with one method, as disclosed in Japanese Patent Publication No. 3-16046, "0"s or "1"s, whichever is greater in number, are output as a decode word; with another method, as disclosed in Japanese Patent Laid open No. 61-128632, a decode word is determined by using the decision by majority of given m.
With these methods, however, the codes having a low degree of likelihood are also determined by majority as decode words, thereby lowering decoding reliability.
Moreover, these methods require long paths for providing a sufficient accuracy, so that it is necessary to make long the path memory in decoding codes having a large constraint length, thereby increasing the amount of necessary hardware to a large extent.